package com.faiz.algorithm;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class FindLessK {
    //设置随机数种子，方便调试
    Random random = new Random(5);

    public int[] getLeastNumbers(int[] arr, int k) {
        int start = 0;
        int end = arr.length - 1;
        int index = partition(arr, start, end);
        while (index != k - 1) {
            if (index > k - 1) {
                end = index - 1;
                index = partition(arr, start, end);
            } else {
                start = index + 1;
                index = partition(arr, start, end);
            }
        }
        int[] result = Arrays.copyOfRange(arr, 0, k);
        return result;
    }

    public int generateRandom(int min, int max) {
        return random.nextInt(max - min + 1) + min;
    }

    public int partition(int[] nums, int start, int end) {
        int index = generateRandom(start, end);
        swap(nums, start, index);
        int i = start;
        int j = end;
        boolean reverseFlag = true;//控制方向
        while (i != j) {
            if (reverseFlag) {
                if (nums[j] < nums[i]) {
                    swap(nums, i, j);
                    reverseFlag = false;
                } else {
                    j--;
                }
            } else {
                if (nums[i] > nums[j]) {
                    swap(nums, i, j);
                    reverseFlag = true;
                } else {
                    i++;
                }
            }
        }
        return i;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;

        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.putIfAbsent(num, 0);
            map.computeIfPresent(num, (k, v) -> v + 1);
        }
    }
}
